package com.cty.ThirtiethDay;
/*
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。

同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。
*/
public class Q_50 {

    // 力扣官方题解 方法一:递归
    /*
    *  思路:
    *    计算当前节点的最大贡献值(对于叶子节点来说 最大贡献值就是本身值
    *    其他节点的最大贡献值是 当前节点 + 子节点的最大的贡献值(如果当前
    *    节点的有两个子节点则选择最大的子节点相加))
    *    时间复杂度O(N) 空间复杂度O(N)
    * */
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        maxGain(root);
        return max;
    }
    private int maxGain(TreeNode root) {
        if (root == null) return 0;
        // 如果是小于0的值直接舍弃
        int leftGain = Math.max(maxGain(root.left),0);
        int rightGain = Math.max(maxGain(root.right),0);

        // 计算最大值
        max = Math.max(max,root.val + rightGain + leftGain);

        // 返回最大贡献值
        return root.val + Math.max(leftGain,rightGain);
    }
}
